package chart;

import java.util.Arrays;

/**
 * 并查集
 * <p>使用双亲表示法来存储一棵树, 每个结点存储其父节点</p>
 * <p>包含合并和查询这两个操作</p>
 * <p>优化：</p>
 * <p>核心思想：使树变得更矮</p>
 * <p>优化合并：小树合到大树, 这样合成的树的高度是大树的高度</p>
 * <p>优化查找：找到结点的根结点后, 将本次查找路径上所有结点的 parent 改成根结点</p>
 *
 * @author yezh
 * @date 2023/7/10 8:43
 */
public class UnionFindSet {

    public static void main(String[] args) {
        UnionFindSet unionAndFind = new UnionFindSet(6);
        unionAndFind.unionOptimize(0, 1);
        unionAndFind.print();
        unionAndFind.unionOptimize(1, 4);
        unionAndFind.print();
        unionAndFind.unionOptimize(2, 3);
        unionAndFind.print();
        unionAndFind.unionOptimize(2, 0);
        unionAndFind.print();
        unionAndFind.findOptimize(3);
        unionAndFind.print();

//        [2, 0, -1, 2, 0, -1]
//        [-2, 0, 0, 2, 0, -1]
    }

    /**
     * 第 i 个结点所在树的根结点
     */
    private int[] parent;

    public UnionFindSet(int n) {
        parent = new int[n];
        Arrays.fill(parent, -1);
    }

    public void union(int e1, int e2) {
        int r1 = find(e1);
        int r2 = find(e2);
        // 将 e2 所在的树合并到 e1 所在树中
        if (r1 != r2) parent[r2] = r1;
    }

    public void unionOptimize(int e1, int e2) {
        // parent[] 中根节点的绝对值是树结点的数量
        int r1 = findOptimize(e1);
        int r2 = findOptimize(e2);
        if (r1 <= r2) {
            parent[r1] += parent[r2];
            parent[r2] = r1;
        } else {
            parent[r2] += parent[r1];
            parent[r1] = r2;
        }
    }

    public int find(int e) {
        // 最坏的时间复杂度: O(n)
        while (parent[e] >= 0)
            // 将 e 指向其父节点
            e = parent[e];
        return e;
    }

    public int findOptimize(int e) {
        // 时间复杂度: O(α(n))
        int r = e;
        while (parent[r] >= 0) r = parent[r];
        int p;
        while (parent[e] >= 0) {
            p = parent[e];
            parent[e] = r;
            e = p;
        }
        return r;
    }

    public void print() {
        System.out.println(Arrays.toString(parent));
    }

}
